|
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for ''all'' possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is ''undecidable'' over Turing machines. It is one of the first examples of a decision problem. Jack Copeland (2004) attributes the term ''halting problem'' to Martin Davis.〔In none of his work did Turing use the word "halting" or "termination". Turing's biographer Hodges does not have the word "halting" or words "halting problem" in his index. The earliest known use of the words "halting problem" is in a proof by Davis (1958, p. 70–71): :"Theorem 2.2 ''There exists a Turing machine whose halting problem is recursively unsolvable''. :"A related problem is the ''printing problem'' for a simple Turing machine Z with respect to a symbol Si". Davis adds no attribution for his proof, so one infers that it is original with him. But Davis has pointed out that a statement of the proof exists informally in Kleene (1952, p. 382). Copeland (2004, p 40) states that: : "The halting problem was so named (and it appears, first stated) by Martin Davis (Copeland footnote 61 )... (It is often said that Turing stated and proved the halting theorem in 'On Computable Numbers', but strictly this is not true)."〕 == Background == The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation, i.e., all programs that can be written in some given programming language that is general enough to be equivalent to a Turing machine. The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations on the amount of memory or time required for the program's execution; it can take arbitrarily long, and use arbitrarily as much storage space, before halting. The question is simply whether the given program will ever halt on a particular input. For example, in pseudocode, the program :while (true) continue does not halt; rather, it goes on forever in an infinite loop. On the other hand, the program :print "Hello, world!" does halt. While deciding whether these programs halt is simple, more complex programs prove problematic. One approach to the problem might be to run the program for some number of steps and check if it halts. But if the program does not halt, it is unknown whether the program will eventually halt or run forever. Turing proved no algorithm can exist which will always correctly decide whether, for a given arbitrary program and its input, the program halts when run with that input; the essence of Turing's proof is that any such algorithm can be made to contradict itself, and therefore cannot be correct. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Halting problem」の詳細全文を読む スポンサード リンク
|